738. 单调递增的数字

Similar Question

Solution Tips

方案一: 模拟

var monotoneIncreasingDigits = function(n) {
    // 将n位数置为 n - 1 时, 要将后面的都设置为 9,这样才是小于而且最大的
    let s = n + '';
    let cur = '';
    let startIndex = 0;
    let i = 0;
    while (i < s.length - 1) {
        if (s[i] < s[i + 1]) {
            // cur += s[i]
            i++;
            startIndex = i;
        }
        else if (s[i] === s[i + 1]) {
            i++;
            // cur += s[i];
        }
        else {
            // cur = cur.slice(0, cur.length - startIndex + 1);
            cur += s.slice(0, startIndex);
            // 只在确定的地方进行拼接好了, 前面两种拼接了还可能会去除
            // 从不等于自己的地方, 减小1, 然后后面的都设置为 9
            s = s[startIndex] - 1 + Array.from({ length: s.length - startIndex - 1 }).fill('9').join('');
            startIndex = 0;
            i = 0;
        }
    }
    // 最后的拼接一下
    cur += s;
    return +cur;
};

方案二: 官解

var monotoneIncreasingDigits = function(n) {
    const strN = n.toString().split('').map(v => +v);
    let i = 1;
    while (i < strN.length && strN[i - 1] <= strN[i]) {
        i += 1;
    }
    if (i < strN.length) {
        while (i > 0 && strN[i - 1] > strN[i]) {
            strN[i - 1] -= 1;
            i -= 1;
        }
        for (i += 1; i < strN.length; ++i) {
            strN[i] = 9;
        }
    }
    return parseInt(strN.join(''));
};

方案三: 从后往前遍历

var monotoneIncreasingDigits = function(n) {
    n = n.toString()
    n = n.split('').map(item => {
        return +item
    })
    let flag = Infinity
    for(let i = n.length - 1; i > 0; i--) {
        if(n [i - 1] > n[i]) {
            flag = i
            n[i - 1] = n[i - 1] - 1
            n[i] = 9
        }
    }

    for(let i = flag; i < n.length; i++) {
        n[i] = 9
    }

    n = n.join('')
    return +n
};